Ordered Level Planarity, Geodesic Planarity and Bi-Monotonicity

摘要

We introduce and study the problem Ordered Level Planarity which asks for aplanar drawing of a graph such that vertices are placed at prescribed positionsin the plane and such that every edge is realized as a y-monotone curve. Thiscan be interpreted as a variant of Level Planarity in which the vertices oneach level appear in a prescribed total order. We establish a complexitydichotomy with respect to both the maximum degree and the level-width, that is,the maximum number of vertices that share a level. Our study of Ordered LevelPlanarity is motivated by connections to several other graph drawing problems. Geodesic Planarity asks for a planar drawing of a graph such that verticesare placed at prescribed positions in the plane and such that every edge isrealized as a polygonal path composed of line segments with two adjacentdirections from a given set $S$ of directions symmetric with respect to theorigin. Our results on Ordered Level Planarity imply $NP$-hardness for any $S$with $|S|\ge 4$ even if the given graph is a matching. Katz, Krug, Rutter andWolff claimed that for matchings Manhattan Geodesic Planarity, the case where$S$ contains precisely the horizontal and vertical directions, can be solved inpolynomial time [GD'09]. Our results imply that this is incorrect unless$P=NP$. Our reduction extends to settle the complexity of the Bi-Monotonicityproblem, which was proposed by Fulek, Pelsmajer, Schaefer and\v{S}tefankovi\v{c}. Ordered Level Planarity turns out to be a special case of T-Level Planarity,Clustered Level Planarity and Constrained Level Planarity. Thus, our resultsstrengthen previous hardness results. In particular, our reduction to ClusteredLevel Planarity generates instances with only two non-trivial clusters. Thisanswers a question posed by Angelini, Da Lozzo, Di Battista, Frati and Roselli.